//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
// Related Topics 数组 二分查找 分治 
// 👍 4959 👎 0


import java.math.BigDecimal;
import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution4 {
    /**
     * 解题思路：
     * 1. 现将两个数组合并为1个数组，从小到大排列
     * 2. 取这一个数组的中位数，如果数组长度/2 为偶数，则取出2个数据除以2即为中位数
     *
     * 解答成功:
     * 			执行耗时:1 ms,击败了100.00% 的Java用户
     * 			内存消耗:42 MB,击败了8.49% 的Java用户
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];

        int idx = 0;
        int idx1 = 0;
        int idx2 = 0;
        while(idx1 != nums1.length && idx2 != nums2.length) {
            int num1 = nums1[idx1];
            int num2 = nums2[idx2];
            if(num1 <= num2) {
                nums[idx] = num1;
                idx1++;
            } else {
                nums[idx] = num2;
                idx2++;
            }
            idx++;
        }
        while(idx1 < nums1.length) {
            nums[idx] = nums1[idx1];
            idx1++;
            idx++;
        }
        while(idx2 < nums2.length) {
            nums[idx] = nums2[idx2];
            idx2++;
            idx++;
        }
        // System.out.println(Arrays.toString(nums));
        if(idx == 0) {
            return 0D;
        }
        int tmp = idx / 2;
        if(idx%2 == 0) {
            return (nums[tmp] + nums[tmp-1]) / 2.0;
        }
        return nums[tmp] / 1.0;
    }

    public static void main(String[] args) {
        System.out.println(new Solution4().findMedianSortedArrays(new int[]{1, 3}, new int[]{2, 4}));
        System.out.println(new Solution4().findMedianSortedArrays(new int[]{1}, new int[]{2, 4}));
        System.out.println(new Solution4().findMedianSortedArrays(new int[]{1,2,3}, new int[]{2}));
        System.out.println(new Solution4().findMedianSortedArrays(new int[]{}, new int[]{2}));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
